home *** CD-ROM | disk | FTP | other *** search
/ The CICA Windows Explosion! / The CICA Windows Explosion! - Disc 1.iso / util / tgrep20.zip / KWSET.C < prev    next >
Text File  |  1994-04-01  |  21KB  |  786 lines
  1. /* kwset.c - search for any of a set of keywords.
  2.    Copyright 1989 Free Software Foundation
  3.           Written August 1989 by Mike Haertel.
  4.  
  5.    This program is free software; you can redistribute it and/or modify
  6.    it under the terms of the GNU General Public License as published by
  7.    the Free Software Foundation; either version 1, or (at your option)
  8.    any later version.
  9.  
  10.    This program is distributed in the hope that it will be useful,
  11.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.    GNU General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU General Public License
  16.    along with this program; if not, write to the Free Software
  17.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  
  19.    The author may be reached (Email) at the address mike@ai.mit.edu,
  20.    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  21.  
  22. /* The algorithm implemented by these routines bears a startling resemblence
  23.    to one discovered by Beate Commentz-Walter, although it is not identical.
  24.    See "A String Matching Algorithm Fast on the Average," Technical Report,
  25.    IBM-Germany, Scientific Center Heidelberg, Tiergartenstrasse 15, D-6900
  26.    Heidelberg, Germany.  See also Aho, A.V., and M. Corasick, "Efficient
  27.    String Matching:  An Aid to Bibliographic Search," CACM June 1975,
  28.    Vol. 18, No. 6, which describes the failure function used below. */
  29.  
  30.  
  31. #include <limits.h>
  32. #include <stdlib.h>
  33. #include <memory.h>
  34. #include <malloc.h>
  35. #include <string.h>
  36.  
  37. #ifdef GREP
  38. extern char *xmalloc(size_t);
  39. #define malloc xmalloc
  40. #endif
  41.  
  42. #include "kwset.h"
  43. #include "obstack.h"
  44.  
  45. #define NCHAR (UCHAR_MAX + 1)
  46. #define obstack_chunk_alloc malloc
  47. #define obstack_chunk_free free
  48.  
  49. /* Balanced tree of edges and labels leaving a given trie node. */
  50. struct tree
  51. {
  52.   struct tree *llink;        /* Left link; MUST be first field. */
  53.   struct tree *rlink;        /* Right link (to larger labels). */
  54.   struct trie *trie;        /* Trie node pointed to by this edge. */
  55.   unsigned char label;        /* Label on this edge. */
  56.   char balance;            /* Difference in depths of subtrees. */
  57. };
  58.  
  59. /* Node of a trie representing a set of reversed keywords. */
  60. struct trie
  61. {
  62.   unsigned int accepting;    /* Word index of accepted word, or zero. */
  63.   struct tree *links;        /* Tree of edges leaving this node. */
  64.   struct trie *parent;        /* Parent of this node. */
  65.   struct trie *next;        /* List of all trie nodes in level order. */
  66.   struct trie *fail;        /* Aho-Corasick failure function. */
  67.   int depth;            /* Depth of this node from the root. */
  68.   int shift;            /* Shift function for search failures. */
  69.   int maxshift;            /* Max shift of self and descendents. */
  70. };
  71.  
  72. /* Structure returned opaquely to the caller, containing everything. */
  73. struct kwset
  74. {
  75.   struct obstack obstack;    /* Obstack for node allocation. */
  76.   int words;            /* Number of words in the trie. */
  77.   struct trie *trie;        /* The trie itself. */
  78.   int mind;            /* Minimum depth of an accepting node. */
  79.   int maxd;            /* Maximum depth of any node. */
  80.   unsigned char delta[NCHAR];    /* Delta table for rapid search. */
  81.   struct trie *next[NCHAR];    /* Table of children of the root. */
  82.   char *target;            /* Target string if there's only one. */
  83.   int mind2;            /* Used in Boyer-Moore search for one string. */
  84.   char *trans;            /* Character translation table. */
  85. };
  86.  
  87. /* Allocate and initialize a keyword set object, returning an opaque
  88.    pointer to it.  Return NULL if memory is not available. */
  89. kwset_t
  90. kwsalloc(trans)
  91.      char *trans;
  92. {
  93.   struct kwset *kwset;
  94.   struct trie *ptrie;
  95.  
  96.   kwset = (struct kwset *) malloc(sizeof (struct kwset));
  97.   if (!kwset)
  98.     return 0;
  99.  
  100.   obstack_init(&kwset->obstack);
  101.   kwset->words = 0;
  102.   ptrie
  103.     = (struct trie *) obstack_alloc(&kwset->obstack, sizeof (struct trie));
  104.   kwset->trie = ptrie;
  105.   if (!kwset->trie)
  106.     {
  107.       kwsfree((kwset_t) kwset);
  108.       return 0;
  109.     }
  110.   ptrie->accepting = 0;
  111.   ptrie->links = 0;
  112.   ptrie->parent = 0;
  113.   ptrie->next = 0;
  114.   ptrie->fail = 0;
  115.   ptrie->depth = 0;
  116.   ptrie->shift = 0;
  117.   kwset->mind = INT_MAX;
  118.   kwset->maxd = -1;
  119.   kwset->target = 0;
  120.   kwset->trans = trans;
  121.  
  122.   return (kwset_t) kwset;
  123. }
  124.  
  125. /* Add the given string to the contents of the keyword set.  Return NULL
  126.    for success, an error message otherwise. */
  127. char *
  128. kwsincr(kws, text, len)
  129.      kwset_t kws;
  130.      char *text;
  131.      size_t len;
  132. {
  133.   struct kwset *kwset;
  134.   register struct trie *trie;
  135.   register unsigned char label;
  136.   register struct tree *link;
  137.   register int depth;
  138.   struct tree *links[12];
  139.   enum { L, R } dirs[12];
  140.   struct tree *t, *r, *l, *rl, *lr;
  141.  
  142.   kwset = (struct kwset *) kws;
  143.   trie = kwset->trie;
  144.   text += len;
  145.  
  146.   /* Descend the trie (built of reversed keywords) character-by-character,
  147.      installing new nodes when necessary. */
  148.   while (len--)
  149.     {
  150.       label = kwset->trans ? kwset->trans[(unsigned char) *--text] : *--text;
  151.  
  152.       /* Descend the tree of outgoing links for this trie node,
  153.      looking for the current character and keeping track
  154.      of the path followed. */
  155.       link = trie->links;
  156.       links[0] = (struct tree *) &trie->links;
  157.       dirs[0] = L;
  158.       depth = 1;
  159.  
  160.       while (link && label != link->label)
  161.     {
  162.       links[depth] = link;
  163.       if (label < link->label)
  164.         dirs[depth++] = L, link = link->llink;
  165.       else
  166.         dirs[depth++] = R, link = link->rlink;
  167.     }
  168.  
  169.       /* The current character doesn't have an outgoing link at
  170.      this trie node, so build a new trie node and install
  171.      a link in the current trie node's tree. */
  172.       if (!link)
  173.     {
  174.       link = (struct tree *) obstack_alloc(&kwset->obstack,
  175.                            sizeof (struct tree));
  176.       if (!link)
  177.         return "memory exhausted";
  178.       link->llink = 0;
  179.       link->rlink = 0;
  180.       link->trie = (struct trie *) obstack_alloc(&kwset->obstack,
  181.                              sizeof (struct trie));
  182.       if (!link->trie)
  183.         return "memory exhausted";
  184.       link->trie->accepting = 0;
  185.       link->trie->links = 0;
  186.       link->trie->parent = trie;
  187.       link->trie->next = 0;
  188.       link->trie->fail = 0;
  189.       link->trie->depth = trie->depth + 1;
  190.       link->trie->shift = 0;
  191.       link->label = label;
  192.       link->balance = 0;
  193.  
  194.       /* Install the new tree node in its parent. */
  195.       if (dirs[--depth] == L)
  196.         links[depth]->llink = link;
  197.       else
  198.         links[depth]->rlink = link;
  199.  
  200.       /* Back up the tree fixing the balance flags. */
  201.       while (depth && !links[depth]->balance)
  202.         {
  203.           if (dirs[depth] == L)
  204.         --links[depth]->balance;
  205.           else
  206.         ++links[depth]->balance;
  207.           --depth;
  208.         }
  209.  
  210.       /* Rebalance the tree by pointer rotations if necessary. */
  211.       if (depth && ((dirs[depth] == L && --links[depth]->balance)
  212.             || (dirs[depth] == R && ++links[depth]->balance)))
  213.         {
  214.           switch (links[depth]->balance)
  215.         {
  216.         case (char) -2:
  217.           switch (dirs[depth + 1])
  218.             {
  219.             case L:
  220.               r = links[depth], t = r->llink, rl = t->rlink;
  221.               t->rlink = r, r->llink = rl;
  222.               t->balance = r->balance = 0;
  223.               break;
  224.             case R:
  225.               r = links[depth], l = r->llink, t = l->rlink;
  226.               rl = t->rlink, lr = t->llink;
  227.               t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;
  228.               l->balance = t->balance != 1 ? 0 : -1;
  229.               r->balance = t->balance != (char) -1 ? 0 : 1;
  230.               t->balance = 0;
  231.               break;
  232.             }
  233.           break;
  234.         case 2:
  235.           switch (dirs[depth + 1])
  236.             {
  237.             case R:
  238.               l = links[depth], t = l->rlink, lr = t->llink;
  239.               t->llink = l, l->rlink = lr;
  240.               t->balance = l->balance = 0;
  241.               break;
  242.             case L:
  243.               l = links[depth], r = l->rlink, t = r->llink;
  244.               lr = t->llink, rl = t->rlink;
  245.               t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;
  246.               l->balance = t->balance != 1 ? 0 : -1;
  247.               r->balance = t->balance != (char) -1 ? 0 : 1;
  248.               t->balance = 0;
  249.               break;
  250.             }
  251.           break;
  252.         }
  253.  
  254.           if (dirs[depth - 1] == L)
  255.         links[depth - 1]->llink = t;
  256.           else
  257.         links[depth - 1]->rlink = t;
  258.         }
  259.     }
  260.  
  261.       trie = link->trie;
  262.     }
  263.  
  264.   /* Mark the node we finally reached as accepting, encoding the
  265.      index number of this word in the keyword set so far. */
  266.   if (!trie->accepting)
  267.     trie->accepting = 1 + 2 * kwset->words;
  268.   ++kwset->words;
  269.  
  270.   /* Keep track of the longest and shortest string of the keyword set. */
  271.   if (trie->depth < kwset->mind)
  272.     kwset->mind = trie->depth;
  273.   if (trie->depth > kwset->maxd)
  274.     kwset->maxd = trie->depth;
  275.  
  276.   return 0;
  277. }
  278.  
  279. /* Enqueue the trie nodes referenced from the given tree in the
  280.    given queue. */
  281. static void
  282. enqueue(
  283.      struct tree *tree,
  284.      struct trie **last)
  285. {
  286.   if (!tree)
  287.     return;
  288.   enqueue(tree->llink, last);
  289.   enqueue(tree->rlink, last);
  290.   (*last) = (*last)->next = tree->trie;
  291. }
  292.  
  293. /* Compute the Aho-Corasick failure function for the trie nodes referenced
  294.    from the given tree, given the failure function for their parent as
  295.    well as a last resort failure node. */
  296. static void
  297. treefails(
  298.      register struct tree *tree,
  299.      struct trie *fail,
  300.      struct trie *recourse)
  301. {
  302.   register struct tree *link;
  303.  
  304.   if (!tree)
  305.     return;
  306.  
  307.   treefails(tree->llink, fail, recourse);
  308.   treefails(tree->rlink, fail, recourse);
  309.  
  310.   /* Find, in the chain of fails going back to the root, the first
  311.      node that has a descendent on the current label. */
  312.   while (fail)
  313.     {
  314.       link = fail->links;
  315.       while (link && tree->label != link->label)
  316.     if (tree->label < link->label)
  317.       link = link->llink;
  318.     else
  319.       link = link->rlink;
  320.       if (link)
  321.     {
  322.       tree->trie->fail = link->trie;
  323.       return;
  324.     }
  325.       fail = fail->fail;
  326.     }
  327.  
  328.   tree->trie->fail = recourse;
  329. }
  330.  
  331. /* Set delta entries for the links of the given tree such that
  332.    the preexisting delta value is larger than the current depth. */
  333. static void
  334. treedelta(
  335.      register struct tree *tree,
  336.      register unsigned int depth,
  337.      unsigned char delta[])
  338. {
  339.   if (!tree)
  340.     return;
  341.   treedelta(tree->llink, depth, delta);
  342.   treedelta(tree->rlink, depth, delta);
  343.   if (depth < delta[tree->label])
  344.     delta[tree->label] = depth;
  345. }
  346.  
  347. /* Return true if A has every label in B. */
  348. static int
  349. hasevery(
  350.      register struct tree *a,
  351.      register struct tree *b)
  352. {
  353.   if (!b)
  354.     return 1;
  355.   if (!hasevery(a, b->llink))
  356.     return 0;
  357.   if (!hasevery(a, b->rlink))
  358.     return 0;
  359.   while (a && b->label != a->label)
  360.     if (b->label < a->label)
  361.       a = a->llink;
  362.     else
  363.       a = a->rlink;
  364.   return !!a;
  365. }
  366.  
  367. /* Compute a vector, indexed by character code, of the trie nodes
  368.    referenced from the given tree. */
  369. static void
  370. treenext(
  371.      struct tree *tree,
  372.      struct trie *next[])
  373. {
  374.   if (!tree)
  375.     return;
  376.   treenext(tree->llink, next);
  377.   treenext(tree->rlink, next);
  378.   next[tree->label] = tree->trie;
  379. }
  380.  
  381. /* Compute the shift for each trie node, as well as the delta
  382.    table and next cache for the given keyword set. */
  383. char *
  384. kwsprep(
  385.      kwset_t kws)
  386. {
  387.   register struct kwset *kwset;
  388.   register int i;
  389.   register struct trie *curr, *fail;
  390.   register char *trans;
  391.   unsigned char delta[NCHAR];
  392.   struct trie *last, *next[NCHAR];
  393.  
  394.   kwset = (struct kwset *) kws;
  395.  
  396.   /* Initial values for the delta table; will be changed later.  The
  397.      delta entry for a given character is the smallest depth of any
  398.      node at which an outgoing edge is labeled by that character. */
  399.   if (kwset->mind < 256)
  400.     for (i = 0; i < NCHAR; ++i)
  401.       delta[i] = kwset->mind;
  402.   else
  403.     for (i = 0; i < NCHAR; ++i)
  404.       delta[i] = 255;
  405.  
  406.   /* Check if we can use the simple boyer-moore algorithm, instead
  407.      of the hairy commentz-walter algorithm. */
  408.   if (kwset->words == 1 && kwset->trans == 0)
  409.     {
  410.       /* Looking for just one string.  Extract it from the trie. */
  411.       kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);
  412.       for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)
  413.     {
  414.       kwset->target[i] = curr->links->label;
  415.       curr = curr->links->trie;
  416.     }
  417.       /* Build the Boyer Moore delta.  Boy that's easy compared to CW. */
  418.       for (i = 0; i < kwset->mind; ++i)
  419.     delta[(unsigned char) kwset->target[i]] = kwset->mind - (i + 1);
  420.       kwset->mind2 = kwset->mind;
  421.       /* Find the minimal delta2 shift that we might make after
  422.      a backwards match has failed. */
  423.       for (i = 0; i < kwset->mind - 1; ++i)
  424.     if (kwset->target[i] == kwset->target[kwset->mind - 1])
  425.       kwset->mind2 = kwset->mind - (i + 1);
  426.     }
  427.   else
  428.     {
  429.       /* Traverse the nodes of the trie in level order, simultaneously
  430.      computing the delta table, failure function, and shift function. */
  431.       for (curr = last = kwset->trie; curr; curr = curr->next)
  432.     {
  433.       /* Enqueue the immediate descendents in the level order queue. */
  434.       enqueue(curr->links, &last);
  435.  
  436.       curr->shift = kwset->mind;
  437.       curr->maxshift = kwset->mind;
  438.  
  439.       /* Update the delta table for the descendents of this node. */
  440.       treedelta(curr->links, curr->depth, delta);
  441.  
  442.       /* Compute the failure function for the decendents of this node. */
  443.       treefails(curr->links, curr->fail, kwset->trie);
  444.  
  445.       /* Update the shifts at each node in the current node's chain
  446.          of fails back to the root. */
  447.       for (fail = curr->fail; fail; fail = fail->fail)
  448.         {
  449.           /* If the current node has some outgoing edge that the fail
  450.          doesn't, then the shift at the fail should be no larger
  451.          than the difference of their depths. */
  452.           if (!hasevery(fail->links, curr->links))
  453.         if (curr->depth - fail->depth < fail->shift)
  454.           fail->shift = curr->depth - fail->depth;
  455.  
  456.           /* If the current node is accepting then the shift at the
  457.          fail and its descendents should be no larger than the
  458.          difference of their depths. */
  459.           if (curr->accepting && fail->maxshift > curr->depth - fail->depth)
  460.         fail->maxshift = curr->depth - fail->depth;
  461.         }
  462.     }
  463.  
  464.       /* Traverse the trie in level order again, fixing up all nodes whose
  465.      shift exceeds their inherited maxshift. */
  466.       for (curr = kwset->trie->next; curr; curr = curr->next)
  467.     {
  468.       if (curr->maxshift > curr->parent->maxshift)
  469.         curr->maxshift = curr->parent->maxshift;
  470.       if (curr->shift > curr->maxshift)
  471.         curr->shift = curr->maxshift;
  472.     }
  473.  
  474.       /* Create a vector, indexed by character code, of the outgoing links
  475.      from the root node. */
  476.       for (i = 0; i < NCHAR; ++i)
  477.     next[i] = 0;
  478.       treenext(kwset->trie->links, next);
  479.  
  480.       if ((trans = kwset->trans) != 0)
  481.     for (i = 0; i < NCHAR; ++i)
  482.       kwset->next[i] = next[(unsigned char) trans[i]];
  483.       else
  484.     for (i = 0; i < NCHAR; ++i)
  485.       kwset->next[i] = next[i];
  486.     }
  487.  
  488.   /* Fix things up for any translation table. */
  489.   if ((trans = kwset->trans) != 0)
  490.     for (i = 0; i < NCHAR; ++i)
  491.       kwset->delta[i] = delta[(unsigned char) trans[i]];
  492.   else
  493.     for (i = 0; i < NCHAR; ++i)
  494.       kwset->delta[i] = delta[i];
  495.  
  496.   return 0;
  497. }
  498.  
  499. #define U(C) ((unsigned char) (C))
  500.  
  501. /* Fast boyer-moore search. */
  502. static char *
  503. bmexec(
  504.      kwset_t kws,
  505.      char *text,
  506.      size_t size)
  507. {
  508.   struct kwset *kwset;
  509.   register unsigned char *d1;
  510.   register char *ep, *sp, *tp;
  511.   register int d, gc, i, len, md2;
  512.  
  513.   kwset = (struct kwset *) kws;
  514.   len = kwset->mind;
  515.  
  516.   if (len == 0)
  517.     return text;
  518.   if (len > size)
  519.     return 0;
  520.   if (len == 1)
  521.     return memchr(text, kwset->target[0], size);
  522.  
  523.   d1 = kwset->delta;
  524.   sp = kwset->target + len;
  525.   gc = U(sp[-2]);
  526.   md2 = kwset->mind2;
  527.   tp = text + len;
  528.  
  529.   /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */
  530.   if (size > 12 * len)
  531.     /* 11 is not a bug, the initial offset happens only once. */
  532.     for (ep = text + size - 11 * len;;)
  533.       {
  534.     while (tp <= ep)
  535.       {
  536.         d = d1[U(tp[-1])], tp += d;
  537.         d = d1[U(tp[-1])], tp += d;
  538.         if (d == 0)
  539.           goto found;
  540.         d = d1[U(tp[-1])], tp += d;
  541.         d = d1[U(tp[-1])], tp += d;
  542.         d = d1[U(tp[-1])], tp += d;
  543.         if (d == 0)
  544.           goto found;
  545.         d = d1[U(tp[-1])], tp += d;
  546.         d = d1[U(tp[-1])], tp += d;
  547.         d = d1[U(tp[-1])], tp += d;
  548.         if (d == 0)
  549.           goto found;
  550.         d = d1[U(tp[-1])], tp += d;
  551.         d = d1[U(tp[-1])], tp += d;
  552.       }
  553.     break;
  554.       found:
  555.     if (U(tp[-2]) == gc)
  556.       {
  557.         for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
  558.           ;
  559.         if (i > len)
  560.           return tp - len;
  561.       }
  562.     tp += md2;
  563.       }
  564.  
  565.   /* Now we have only a few characters left to search.  We
  566.      carefully avoid ever producing an out-of-bounds pointer. */
  567.   ep = text + size;
  568.   d = d1[U(tp[-1])];
  569.   while (d <= ep - tp)
  570.     {
  571.       d = d1[U((tp += d)[-1])];
  572.       if (d != 0)
  573.     continue;
  574.       if (tp[-2] == gc)
  575.     {
  576.       for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
  577.         ;
  578.       if (i > len)
  579.         return tp - len;
  580.     }
  581.       d = md2;
  582.     }
  583.  
  584.   return 0;
  585. }
  586.  
  587. /* Hairy multiple string search. */
  588. static char *
  589. cwexec(
  590.      kwset_t kws,
  591.      char *text,
  592.      size_t len,
  593.      struct kwsmatch *kwsmatch)
  594. {
  595.   struct kwset *kwset;
  596.   struct trie **next, *trie, *accept;
  597.   char *beg, *lim, *mch, *lmch;
  598.   register unsigned char c, *delta;
  599.   register int d;
  600.   register char *end, *qlim;
  601.   register struct tree *tree;
  602.   register char *trans;
  603.  
  604.   /* Initialize register copies and look for easy ways out. */
  605.   kwset = (struct kwset *) kws;
  606.   if (len < kwset->mind)
  607.     return 0;
  608.   next = kwset->next;
  609.   delta = kwset->delta;
  610.   trans = kwset->trans;
  611.   lim = text + len;
  612.   end = text;
  613.   if ((d = kwset->mind) != 0)
  614.     mch = 0;
  615.   else
  616.     {
  617.       mch = text, accept = kwset->trie;
  618.       goto match;
  619.     }
  620.  
  621.   if (len >= 4 * kwset->mind)
  622.     qlim = lim - 4 * kwset->mind;
  623.   else
  624.     qlim = 0;
  625.  
  626.   while (lim - end >= d)
  627.     {
  628.       if (qlim && end <= qlim)
  629.     {
  630.       end += d - 1;
  631.       while ((d = delta[c = *end]) && end < qlim)
  632.         {
  633.           end += d;
  634.           end += delta[(unsigned char) *end];
  635.           end += delta[(unsigned char) *end];
  636.         }
  637.       ++end;
  638.     }
  639.       else
  640.     d = delta[c = (end += d)[-1]];
  641.       if (d)
  642.     continue;
  643.       beg = end - 1;
  644.       trie = next[c];
  645.       if (trie->accepting)
  646.     {
  647.       mch = beg;
  648.       accept = trie;
  649.     }
  650.       d = trie->shift;
  651.       while (beg > text)
  652.     {
  653.       c = trans ? trans[(unsigned char) *--beg] : *--beg;
  654.       tree = trie->links;
  655.       while (tree && c != tree->label)
  656.         if (c < tree->label)
  657.           tree = tree->llink;
  658.         else
  659.           tree = tree->rlink;
  660.       if (tree)
  661.         {
  662.           trie = tree->trie;
  663.           if (trie->accepting)
  664.         {
  665.           mch = beg;
  666.           accept = trie;
  667.         }
  668.         }
  669.       else
  670.         break;
  671.       d = trie->shift;
  672.     }
  673.       if (mch)
  674.     goto match;
  675.     }
  676.   return 0;
  677.  
  678.  match:
  679.   /* Given a known match, find the longest possible match anchored
  680.      at or before its starting point.  This is nearly a verbatim
  681.      copy of the preceding main search loops. */
  682.   if (lim - mch > kwset->maxd)
  683.     lim = mch + kwset->maxd;
  684.   lmch = 0;
  685.   d = 1;
  686.   while (lim - end >= d)
  687.     {
  688.       if ((d = delta[c = (end += d)[-1]]) != 0)
  689.     continue;
  690.       beg = end - 1;
  691.       if (!(trie = next[c]))
  692.     {
  693.       d = 1;
  694.       continue;
  695.     }
  696.       if (trie->accepting && beg <= mch)
  697.     {
  698.       lmch = beg;
  699.       accept = trie;
  700.     }
  701.       d = trie->shift;
  702.       while (beg > text)
  703.     {
  704.       c = trans ? trans[(unsigned char) *--beg] : *--beg;
  705.       tree = trie->links;
  706.       while (tree && c != tree->label)
  707.         if (c < tree->label)
  708.           tree = tree->llink;
  709.         else
  710.           tree = tree->rlink;
  711.       if (tree)
  712.         {
  713.           trie = tree->trie;
  714.           if (trie->accepting && beg <= mch)
  715.         {
  716.           lmch = beg;
  717.           accept = trie;
  718.         }
  719.         }
  720.       else
  721.         break;
  722.       d = trie->shift;
  723.     }
  724.       if (lmch)
  725.     {
  726.       mch = lmch;
  727.       goto match;
  728.     }
  729.       if (!d)
  730.     d = 1;
  731.     }
  732.  
  733.   if (kwsmatch)
  734.     {
  735.       kwsmatch->index = accept->accepting / 2;
  736.       kwsmatch->beg[0] = mch;
  737.       kwsmatch->size[0] = accept->depth;
  738.     }
  739.   return mch;
  740. }
  741.   
  742. /* Search through the given text for a match of any member of the
  743.    given keyword set.  Return a pointer to the first character of
  744.    the matching substring, or NULL if no match is found.  If FOUNDLEN
  745.    is non-NULL store in the referenced location the length of the
  746.    matching substring.  Similarly, if FOUNDIDX is non-NULL, store
  747.    in the referenced location the index number of the particular
  748.    keyword matched. */
  749. char *
  750. kwsexec(
  751.      kwset_t kws,
  752.      char *text,
  753.      size_t size,
  754.      struct kwsmatch *kwsmatch)
  755. {
  756.   struct kwset *kwset;
  757.   char *ret;
  758.  
  759.   kwset = (struct kwset *) kws;
  760.   if (kwset->words == 1 && kwset->trans == 0)
  761.     {
  762.       ret = bmexec(kws, text, size);
  763.       if (kwsmatch != 0 && ret != 0)
  764.     {
  765.       kwsmatch->index = 0;
  766.       kwsmatch->beg[0] = ret;
  767.       kwsmatch->size[0] = kwset->mind;
  768.     }
  769.       return ret;
  770.     }
  771.   else
  772.     return cwexec(kws, text, size, kwsmatch);
  773. }
  774.  
  775. /* Free the components of the given keyword set. */
  776. void
  777. kwsfree(
  778.      kwset_t kws)
  779. {
  780.   struct kwset *kwset;
  781.  
  782.   kwset = (struct kwset *) kws;
  783.   obstack_free(&kwset->obstack, 0);
  784.   free(kws);
  785. }
  786.